package BinaryTree;

import java.util.LinkedList;
import java.util.Queue;
/**
 * 给定一个二叉树，确定他是否是一个完全二叉树。
 *
 * 完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
 *
 * 数据范围：节点数满足 1≤n≤100
 *
 * */

class BM35 {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     使用层次遍历，每一层从左到右遍历节点。

     由于判断完全二叉树，当遍历当前层时如果遇到空节点，如果该空节点右侧还有节点，
     说明该树一定不是完全二叉树，直接返回false，遍历完返回true；
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        //标记空节点
        boolean left =  true;
        if(root == null)
            return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode nowNode = queue.poll();
            //说明当前节点是空节点
            if(nowNode == null){
                left = false;
            }else{
                // 说明前面节点有空的，肯定不是完全
                if(left == false)
                    return false;
                queue.offer(nowNode.left);
                queue.offer(nowNode.right);
            }
        }
        return true;
    }
}
